package Algorithm.LinkedListProblem;

/**
 * @Author cj
 * @Date 2022/1/12 22:19
 */
public class relocate {

    static class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    public static Node relocate1(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node mid = head, fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            mid = mid.next;
        }
        Node cur1 = head, cur2 = mid.next;
        mid.next = null;
        mergeLR(cur1, cur2);
        return head;
    }

    private static void mergeLR(Node cur1, Node cur2) {
        Node next = null;
        while (cur1.next != null) {
            next = cur2.next;
            cur1.next = cur2;
            cur2.next = cur1.next;
            cur1 = cur2.next;
            cur2 = next;
        }
        cur1.next = cur2;
    }

}
